Ông xuất thân từ một gia đình lao động nghèo thuộc làng An Cư, huyện Triệu Phong, tỉnh Quảng Trị.

Với các tài liệu Đại Nam thực lục chính biên và Quốc triều hương khoa lục, người đời sau nhận thấy:

1. Trần Tiễn Thành và Quốc sử quán ghi chép: Vào năm Thiệu Trị thứ 2 (1842), tại trường thi Thừa Thiên, có một sĩ tử người Quảng Trị, đã thi đỗ tú tài, nhưng bị phát hiện tên trùng với quốc tính. Dưới triều Minh Mạng đã có sắc dụ, ai mang họ Nguyễn mà tên kép có lót chữ Phước (Phúc), thì phải đổi chữ lót ấy. Nhưng sĩ tử họ Nguyễn, tên Phước Tường này lại không chịu đổi. Do đó, người tú tài tân khoa phải bị gạch tên trong danh sách trúng tuyển và đồng thời bị tội đồ (đày nơi gần) một năm.
2. Về kì thi hương vào năm Tự Đức thứ 3 (1850), sự cố chữ "Phúc" lại được Cao Xuân Dục và Quốc sử quán triều Nguyễn ghi chép như sau: "Nguyễn Văn Tường, người xã An Cư, huyện Đăng Xương [Triệu Phong - chua thêm], tỉnh Quảng Trị. Nguyên tên là Nguyễn Phước Tường; vì tên trùng với quốc tính, không chịu đổi, nên bị đi đày; hết hạn lại được phục hàm cử nhân".

Như vậy, có thể lần thứ hai này, Nguyễn Văn Tường chỉ bị "nhắc lại" án cũ, hồi ông mới 18 tuổi (1842).